// https://www.lintcode.com/problem/linked-list-cycle/description

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
     
    // 链表的环肯定是在最后，因为只有一个next指针
    // 判断有环：快慢指针，快指针速度是慢指针两倍，只要都进环，就一定会相遇
    // 找环的起点：相遇时快指针比慢指针多跑的是环的倍数，也是慢指针跑的距离。因此慢指针跑的距离是环的倍数。
    // 此时一个指针停留在相遇处，另一个从head开始，两个指针一起用相同的速度跑。因为第一个指针比第二个多跑的是环的倍数
    // ，所以当跑到环地点时候两个指针相遇。
    bool hasCycle(ListNode * head) {
        // ListNode * p1 = head;
        // ListNode * p2 = head;
        // while (p1 && p1->next)
        // {
        //     p2 = p2->next;
        //     p1 = p1->next->next;
        //     if (p1 == p2)
        //     {
        //         return true;
        //     }
        // }

        unordered_set<ListNode*> s; 
        while (head != NULL) { 
            if (s.find(head) != s.end()) 
                return true; 
            s.insert(head); 
      
            head = head->next; 
        } 
        return false;
    }
};